Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 41/115

Q: What will be the resulting array after rotating arr[]={1, 2, 3, 4, 5} by 2?
A. 2, 1, 3, 4, 5
B. 3, 4, 5, 1, 2
C. 4, 5, 1, 2, 3
D. 1, 2, 3, 5, 4
Solution: When the given array is rotated by 2 then the resulting array will be
Rotation 1: {2,3,4,5,1}
Rotation 2: {3,4,5,1,2}.
Thus, the final array is {3,4,5,1,2}.
Q: What will be the output of the following code?

#include 
using namespace std;
int main()
{   
    int arr[] = {1,2,3,4,5,6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int d=4;
    int temp[10];
 
    for(int i=0;i
A. 5 6 1 2 3 4
B. 6 5 4 3 1 2
C. 3 4 5 6 1 2
D. error
Solution: The given code rotates the given array by 4. It does so by using an array temp[] which stores the first d elements and then shift them to the end of the array. So the output will be 5 6 1 2 3 4.
Q: What will be the time complexity of the following code?

#include 
using namespace std;
int main()
{   
    int arr[] = {1,2,3,4,5,6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int d=4;
    int temp[10];
 
    for(int i=0;i
A. O(d)
B. O(n)
C. O(n2)
D. O(n*d)
Solution: The given code rotates an input array by d. The longest loop in the code takes n iterations so the time complexity will be O(n).
Q: What will be the auxiliary space complexity of the following code?

#include 
using namespace std;
int main()
{   
    int arr[] = {1,2,3,4,5,6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int d=4;
    int temp[10];
 
    for(int i=0;i
A. O(1)
B. O(n)
C. O(d)
D. O(n*d)
Solution: The given code rotates an input array by d. It does so by using an auxiliary array temp[] which stores first d elements of the original array. So the auxiliary space complexity will be O(d).
Q: What will be the output of the following code?

#include  
using namespace std; 
 
void func1(int arr[], int n) 
{ 
	int k = arr[0], i; 
	for (i = 0; i < n - 1; i++) 
		arr[i] = arr[i + 1]; 
 
	arr[i] = k; 
} 
 
void func(int arr[], int d, int n) 
{ 
	for (int i = 0; i < d; i++) 
		func1(arr, n); 
} 
 
void printArray(int arr[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
} 
 
int main() 
{ 
	int arr[] = { 1, 2, 3, 4, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
 
 
	func(arr, 3, n); 
	printArray(arr, n); 
 
	return 0; 
}
A. 4 5 1 2 3
B. 3 4 5 1 2
C. 5 4 3 1 2
D. error
Solution: The given code rotates the input array by 3. It does so by rotating the elements one by one until the desired rotation is achieved. So the output will be 4 5 1 2 3.
Q: What will be the time complexity of the following code?

#include  
using namespace std; 
void func1(int arr[], int n) 
{ 
	int k = arr[0], i; 
	for (i = 0; i < n - 1; i++) 
		arr[i] = arr[i + 1]; 
 
	arr[i] = k; 
} 
 
void func(int arr[], int d, int n) 
{ 
	for (int i = 0; i < d; i++) 
		func1(arr, n); 
} 
 
void printArray(int arr[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
} 
 
int main() 
{ 
	int arr[] = { 1, 2, 3, 4, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
 
    int d = 3;
	func(arr, d, n); 
	printArray(arr, n); 
 
	return 0; 
}
A. O(n*d)
B. O(n)
C. O(d)
D. O(n2)
Solution: The given code rotates the input array by d. It does so by rotating the elements one by one until the desired rotation is achieved. Each element takes O(n) time for rotation and there are d such elements in the array. So the time complexity would be O(n*d).
Q: What will be the auxiliary space complexity of the following code?

#include  
using namespace std; 
void func1(int arr[], int n) 
{ 
	int k = arr[0], i; 
	for (i = 0; i < n - 1; i++) 
		arr[i] = arr[i + 1]; 
 
	arr[i] = k; 
} 
 
void func(int arr[], int d, int n) 
{ 
	for (int i = 0; i < d; i++) 
		func1(arr, n); 
} 
 
void printArray(int arr[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
} 
 
int main() 
{ 
	int arr[] = { 1, 2, 3, 4, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
 
    int d = 3;
	func(arr, d, n); 
	printArray(arr, n); 
 
	return 0; 
}
A. O(1)
B. O(n)
C. O(d)
D. O(n*d)
Solution: The given code rotates the input array by d. It does so by rotating the elements one by one until the desired rotation is achieved. It does not require any auxiliary array for this purpose. So the auxiliary space complexity will be O(1).
Q: To rotate an array by using the algorithm of rotating its elements one by one is an in place algorithm.
A. true
B. false
C. ...
D. ...
Solution: The auxiliary space requirement of the mentioned algorithm is O(1). So it qualifies to be an in place algorithm.
Q: What will be the output of the following code?

#include  
using namespace std; 
void func1(int arr[], int left, int right) 
{ 
	while (left < right) 
	{ 
		int temp = arr[left]; 
		arr[left] = arr[right]; 
		arr[right] = temp; 
		left++; 
		right--; 
	} 
} 
 
void func(int arr[], int d, int n) 
{ 
	func1(arr, 0, d-1); 
	func1(arr, d, n-1); 
	func1(arr, 0, n-1); 
} 
 
void printArray(int arr[], int size) 
{ 
	for (int i = 0; i < size; i++) 
	cout << arr[i] << " "; 
} 
 
int main() 
{ 
	int arr[] = {1, 2, 3, 4, 5}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int d = 2; 
	func(arr, d, n); 
	printArray(arr, n); 
 
	return 0; 
}
A. 3 2 1 4 5
B. 3 4 5 1 2
C. 5 4 3 2 1
D. error
Solution: The given code rotates the input array by 2. It does so by applying a reversal algorithm to different segments of the array. First d elements and the rest of the array is reversed individually. Then the whole array is reversed which gives us the desired rotated array. So the output will be 3 4 5 1 2.
Q: What will be the auxiliary space complexity of the code to rotate an array by using the reversal algorithm (d = number of rotations)?
A. O(1)
B. O(n)
C. O(d)
D. O(n*d)
Solution: The reversal algorithm for rotating an array does not require any auxiliary space. So the auxiliary space complexity will be O(1).

You Have Score    /10